{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FAQ for Binary Tree\n",
    "\n",
    "[切换为简体中文][1] ｜ [@mjd507][2]\n",
    "\n",
    "[1]: https://mp.weixin.qq.com/s/NaT0uFK2jHXmtPRBL90Lfw\n",
    "[2]: https://github.com/mjd507\n",
    "\n",
    "![Logo](images/BT-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The daily update of the *Daily Problem* has been going on for 66 days. The number of followers has gradually increased, and the WeChat Group has gradually become active. This is a good start and I hope everyone can stick to it as I do.\n",
    "\n",
    "This week I encountered several problems related to the binary tree. I won't push any question today, but will sort out the basic questions related to the binary tree. Also, make sure everyone enjoy it!\n",
    "\n",
    "First of all, let's have a summary:\n",
    "\n",
    "- *Tree* is a data structure which have levels in it. It has parents and childs, but different from a *graph*.\n",
    "- *Binary tree* has 2 childs at most - a *left subtree* and a *right subtree*.\n",
    "- There're 3 ways to traverse a binary tree. All of them are based on *Depth First Search*:\n",
    "    - Pre-order Traversal: `root` -> `left subtree` -> `right subtree`\n",
    "    - In-order Traversal: `left subtree` -> `root` -> `right subtree`\n",
    "    - Post-order Traversal: `left subtree` -> `right subtree` -> `root`\n",
    "- You can use both iterative or recursive way to traverse a binary tree.\n",
    "- Or you can use *Broad First Search*, which is *Level-order Traversal*, to traverse a binary tree.\n",
    "\n",
    "Here we prepared 6 questions for you, we recommend you to write them down if you're free.\n",
    "\n",
    "- [Pre-order Traversal](#Pre-order-Traversal) (Both recursive and iterative)\n",
    "- [In-order Traversal](#In-order-Traversal) (Both recursive and iterative)\n",
    "- [Post-order Traversal](#Post-order-Traversal) (Both recursive and iterative)\n",
    "- [Broad-first Traversal](#Broad-first-Traversal)\n",
    "- [The maximun depth of a binary tree](#The-maximum-depth-of-a-binary-tree)\n",
    "- [Judging a symmetric (mirrored) binary tree][1] (Both recursive and iterative)\n",
    "\n",
    "[1]: #Judging-a-symmetric-(mirrored)-binary-tree\n",
    "\n",
    "The following code in Python3 was converted from the JavaScript version by [@mjd507](https://github.com/mjd507), which has spent him for a week. If there're mistakes, please point out. Thank you!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pre-order Traversal\n",
    "\n",
    "Given a binary tree seem like below, it should return `123`.\n",
    "\n",
    "```text\n",
    "1\n",
    " \\\n",
    "  2\n",
    " /\n",
    "3\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pre_Order:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def recursivly(self, tree: Node) -> str:\n",
    "        if tree is None:\n",
    "            return ''\n",
    "        result = [\n",
    "            str(tree.value),\n",
    "            self.recursivly(tree.left),\n",
    "            self.recursivly(tree.right)\n",
    "        ]\n",
    "        return ''.join(result)\n",
    "\n",
    "    def iterativly(self, tree: Node) -> str:\n",
    "        stack = [tree]\n",
    "        result = []\n",
    "        while stack != []:\n",
    "            root = stack[-1]\n",
    "            stack.pop()\n",
    "            result.append(str(root.value))\n",
    "            if root.right:\n",
    "                stack.append(root.right)\n",
    "            if root.left:\n",
    "                stack.append(root.left)\n",
    "        return ''.join(result)\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tree = self.Node(1, right=self.Node(2, left=self.Node(3)))\n",
    "\n",
    "\n",
    "demo = Pre_Order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'123'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.recursivly(demo.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'123'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.iterativly(demo.tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In-order Traversal\n",
    "\n",
    "Given a binary tree seems like below, it should return `132`.\n",
    "\n",
    "To realize the iteration, you need to a stack and a pointer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class In_Order:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def recursivly(self, tree: Node) -> str:\n",
    "        if tree is None:\n",
    "            return ''\n",
    "        result = [\n",
    "            self.recursivly(tree.left),\n",
    "            str(tree.value),\n",
    "            self.recursivly(tree.right)\n",
    "        ]\n",
    "        return ''.join(result)\n",
    "\n",
    "    def iterativly(self, tree: Node) -> str:\n",
    "        # Define a stack\n",
    "        stack = []\n",
    "        # Define current pointer\n",
    "        current = tree\n",
    "        result = []\n",
    "        while current is not None or len(stack) != 0:\n",
    "            while current is not None:\n",
    "                stack.append(current)\n",
    "                current = current.left\n",
    "            # When current is None, ...\n",
    "            current = stack[-1]\n",
    "            result.append(str(current.value))\n",
    "            stack.pop()\n",
    "            current = current.right\n",
    "        # Until current is None and stack is empty.\n",
    "        return ''.join(result)\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.tree = self.Node(1, right=self.Node(2, left=self.Node(3)))\n",
    "\n",
    "\n",
    "demo = In_Order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'132'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.recursivly(demo.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'132'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.iterativly(demo.tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Post-order Traversal\n",
    "\n",
    "Given a binary tree like following, it should return `321`.\n",
    "\n",
    "```text\n",
    "1\n",
    " \\\n",
    "  2\n",
    " /\n",
    "3\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Post_Order:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def recursivly(self, tree: Node) -> str:\n",
    "        if tree is None:\n",
    "            return ''\n",
    "        result = [\n",
    "            self.recursivly(tree.left),\n",
    "            self.recursivly(tree.right),\n",
    "            str(tree.value)\n",
    "        ]\n",
    "        return ''.join(result)\n",
    "\n",
    "    def iterativly(self, tree: Node) -> str:\n",
    "        # Use 2 stacks.\n",
    "        stack_A = [tree]\n",
    "        stack_B = []\n",
    "        while stack_A != []: \n",
    "            node = stack_A[-1]\n",
    "            stack_B.append(node)\n",
    "            stack_A.pop()\n",
    "            if node.left is not None:\n",
    "                stack_A.append(node.left)\n",
    "            if node.right is not None:\n",
    "                stack_A.append(node.right)\n",
    "        stack_B.reverse()\n",
    "        return ''.join([str(elem.value) for elem in stack_B])\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tree = self.Node(1, right=self.Node(2, left=self.Node(3)))\n",
    "\n",
    "\n",
    "demo = Post_Order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'321'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.recursivly(demo.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'321'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.iterativly(demo.tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Broad-first Traversal\n",
    "\n",
    "Given a binary tree as follows, it should return `12345`.\n",
    "\n",
    "```text\n",
    "#   1\n",
    "#  / \\\n",
    "# 2   3\n",
    "#    / \\\n",
    "#   4   5\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BFS_Traversal:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def traverse(self, tree: Node) -> list:\n",
    "        queue = [{'tree': tree, 'height': 1}]\n",
    "        result = []\n",
    "        map_ = {}\n",
    "        while queue != []:\n",
    "            node = queue[0]\n",
    "            queue.pop(0)\n",
    "            if node['height'] not in map_.keys():\n",
    "                map_[node['height']] = True\n",
    "                result.append([])\n",
    "            result[node['height'] - 1].append(node['tree'].value)\n",
    "            if node['tree'].left is not None:\n",
    "                queue.append({\n",
    "                    'tree': node['tree'].left,\n",
    "                    'height': node['height'] + 1\n",
    "                })\n",
    "            if node['tree'].right is not None:\n",
    "                queue.append({\n",
    "                    'tree': node['tree'].right,\n",
    "                    'height': node['height'] + 1\n",
    "                })\n",
    "        return result\n",
    "\n",
    "    def test(self):\n",
    "        tree = self.Node(\n",
    "            1, self.Node(2),\n",
    "            self.Node(3, self.Node(4), self.Node(5))\n",
    "        )\n",
    "        return self.traverse(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [2, 3], [4, 5]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BFS_Traversal().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The maximum depth of a binary tree\n",
    "\n",
    "Given a binary tree, find its maximum depth.\n",
    "\n",
    "> The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.\n",
    ">\n",
    "> **Note:** A *leaf* is a node with no children.\n",
    "\n",
    "The following binary tree should return `3`.\n",
    "\n",
    "```text\n",
    "#     1\n",
    "#    / \\\n",
    "#   2   3\n",
    "#  / \\\n",
    "# 4   5\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Max_Depth:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def check(self, tree: Node):\n",
    "        if tree is None:\n",
    "            return 0\n",
    "        return max(self.check(tree.left) + 1, self.check(tree.right) + 1)\n",
    "\n",
    "    def test(self):\n",
    "        tree = self.Node(\n",
    "            1, self.Node(2),\n",
    "            self.Node(3, self.Node(4), self.Node(5))\n",
    "        )\n",
    "        return self.check(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Max_Depth().test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Judging a symmetric (mirrored) binary tree\n",
    "\n",
    "Given a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).\n",
    "\n",
    "For example, this binary tree is symmetric:\n",
    "\n",
    "```text\n",
    "#      1\n",
    "#    /   \\\n",
    "#   2     2\n",
    "#  / \\   / \\\n",
    "# 3   4 4   3\n",
    "```\n",
    "\n",
    "But this one isn't:\n",
    "\n",
    "```text\n",
    "#   1\n",
    "#  / \\\n",
    "# 2   2\n",
    "#  \\   \\\n",
    "#   3   3\n",
    "```\n",
    "\n",
    "Solve it in both recursivly and iterativly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Symmetric_Tree:\n",
    "    class Node:\n",
    "        def __init__(self, value, left=None, right=None):\n",
    "            self.value = value\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "\n",
    "    def recursivly(self, tree_A: Node, tree_B: Node) -> bool:\n",
    "        if tree_A is None and tree_B is None:\n",
    "            return True\n",
    "        if not (tree_A and tree_B):\n",
    "            return False\n",
    "        if tree_A.value != tree_B.value:\n",
    "            return False\n",
    "        is_left_symmetric = self.recursivly(tree_A.left, tree_B.right)\n",
    "        is_right_symmetric = self.recursivly(tree_A.right, tree_B.left)\n",
    "        return (is_left_symmetric and is_right_symmetric)\n",
    "\n",
    "    def iterativly(self, tree: Node) -> bool:\n",
    "        if tree is None:\n",
    "            return True\n",
    "        if tree.left is None and tree.right is None:\n",
    "            return True\n",
    "        queue = []\n",
    "        queue.append(tree)\n",
    "        queue.append(tree)\n",
    "        while queue != []:\n",
    "            left_node = queue[0]\n",
    "            queue.pop(0)\n",
    "            right_node = queue[0]\n",
    "            queue.pop(0)\n",
    "            if left_node.value != right_node.value:\n",
    "                return False\n",
    "            if left_node.left and right_node.right:\n",
    "                queue.append(left_node.left)\n",
    "                queue.append(right_node.right)\n",
    "            elif left_node.left or right_node.right:\n",
    "                return False\n",
    "            if left_node.right and right_node.left:\n",
    "                queue.append(left_node.right)\n",
    "                queue.append(right_node.left)\n",
    "            elif left_node.right or right_node.left:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tree_A = self.Node(1)\n",
    "        self.tree_A.left = self.Node(2, self.Node(3), self.Node(4))\n",
    "        self.tree_A.right = self.Node(2, self.Node(4), self.Node(3))\n",
    "        self.tree_B = self.Node(1)\n",
    "        self.tree_B.left = self.Node(2, right=self.Node(3))\n",
    "        self.tree_B.right = self.Node(2, right=self.Node(3))\n",
    "\n",
    "\n",
    "demo = Symmetric_Tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.recursivly(demo.tree_A, demo.tree_A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.iterativly(demo.tree_A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.recursivly(demo.tree_B, demo.tree_B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "demo.iterativly(demo.tree_B)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
